The invention relates generally to a method and system for managing dynamic resources, and, more specifically, to a method and system for threaded resource allocation and reclamation.
An operating system is a set of computer programs that interact with a computer system to provide services and resources requested by application programs. An example of a resource provided by operating systems is a memory segment selector (xe2x80x9cselectorsxe2x80x9d). Selectors are resources used in computers based on the Intel 80xc3x9786 series of microprocessors to virtualize the primary storage address space, allowing primary storage contents to be rearranged in primary storage and improving robustness by preventing applications from accidentally overwriting memory that they do not own. FIG. 1 is a diagram demonstrating the use of a selector. The diagram shows an address space 110 used to store and retrieve data. Programs use pointers to store data in and retrieve data from one or more storage devices to which linear addresses within the address space are mapped. Some programs use xe2x80x9csegmented pointersxe2x80x9d (also called xe2x80x9cfar pointersxe2x80x9d) to store and retrieve data. Segmented pointers like pointer 120 are comprised of two parts: a selector identifier (e.g., segment identifier 121) and an offset (e.g., offset 122). The selectors available in a computer system are stored together in a local descriptor table (xe2x80x9cLDTxe2x80x9d) like LDT 130. The selector identifier of a segmented pointer identifies a selector stored in the LDT. For example, the selector identifier 121 (xe2x80x9c0x0050xe2x80x9d) identifies selector 131. Usually the selector identifier is not actually stored in the LDT, but rather it constitutes an offset from the beginning of the LDT to the portion of the LDT corresponding to a particular selector, for example, selector 131 is the selector stored beginning at the 0x0050th byte of the LDT. Each selector identifies a xe2x80x9csegmentxe2x80x9d of the address space by containing a representation of a base address within the address space at which that segment begins. For example, selector 131 contains a base representation 133 of xe2x80x9c0x0100000xe2x80x9d, which represents linear address 0x01000000. Selector 131 therefore identifies segment 111, which begins at linear addresses 0x01000000 (the base) and continues to 0x0100FFFF (the base plus a maximum length value). The linear address referred to by a segmented pointer is consequently the sum of the base represented by the selector identified by the segment identifier of the segmented pointer and offset of the segmented pointer. As an example, the segmented pointer 120 refers to linear address 112 (xe2x80x9c0x01008000xe2x80x9d).
In many operating systems, selectors are frequently allocated and released. For instance, whenever the operating system allocates a block of memory within the address space for an application that uses segmented pointers, it allocates a new selector and sets its base to the linear address at the beginning of the block. The operating system then returns a segmented pointer to the application comprised of the identifier of the allocated selector and the offset zero. When the application frees the block, the operating system frees the selector. Selectors are especially frequently allocated and released in hybrid operating systems in which both application that use segmented pointers and applications that use flat pointers containing a linear address. When an application that uses flat pointers attempts to pass a flat pointer containing a linear address to an application that uses segmented pointers, the operating system allocates a new selector and sets its base to the linear address. The operating system then passes a segmented pointer to the application comprised of the identifier of the allocated selector and the offset zero. When the application that receives the segmented pointer no longer needs it, the operating system frees the selector.
Because virtually every type of resource provided to application programs is scarce within the computer system, an operating system must allocate and reclaim resources in a way that maximizes their availability to application programs. Further, because applications request some types of resources frequently in a typical computer system, the portion of the operating system that responds to requests to allocate and reclaim resources must operate efficiently.
Both of these goals for resource allocation are more difficult to achieve in a multithreaded operating system. Multithreaded operating systems appear to execute several application programs at once by maintaining multiple execution contexts (typically at least one for each active application), each comprised of separate program counters and register values. Each execution context is said to correspond to a different thread. Typically, in multithreaded operating system running on a single processor, one thread at a time may be active and execute instructions. Such a multithreaded operating system provides concurrent processing of the threads, that is, the illusion of simultaneous processing, by frequently changing the execution context so that each thread, in turn, is the active thread and executes instructions for a brief period.
FIGS. 2A-2C are allocation diagrams that demonstrate a common conventional approach to resource allocation and reclamation in a multithreaded operating system. FIG. 2A shows that 16 selectors, numbered 0x0001-0x0010, are available within a computer system. Some of these selectors are in use by a thread, while the others are unused, or xe2x80x9cfree.xe2x80x9d Each thread that exists in the computer system is represented by a box bounded with broken lines. Box 210 shows that selector 0x0001 is in use by thread 1; box 220 shows that selector 0x0002 is in use by thread 2; and box 230 shows that thread 3 is not currently using any selectors. The other 14 selectors, 0x0003-0x0010, are free, and are stored in a structure called the free list. The free list is a linked list 240, which has a head 241 that points to the first item. The first item corresponds to selector 0x0003, and contains a pointer to the next item, which corresponds to selector 0x0004. The free list is terminated by a null pointer stored in the last item, which corresponds to selector 0x0010.
FIG. 2B is an allocation diagram that demonstrates the allocation of a free selector. When thread 3 requests the allocation of a selector, the approach removes the first item of the list, 0x0003, and allocates the associated selector to thread 3. Selector 0x0003 therefore appears in the box for thread three, box 230. The first item is removed from the free list by copying the pointer in the head to the first item for the requesting thread, then copying the pointer in the first item into the head.
FIG. 2C is an allocation diagram that demonstrates the reclamation of a freed selector. When thread 2 finishes using selector 0x0002, it frees selector 0x0002 by requesting its reclamation, and the approach adds an item to the free list representing the reclaimed selector. The item is added to the free list by creating an item representing the reclaimed selector, copying the pointer in the head into the created item, and replacing the pointer in the head with a pointer to the created item.
Removing an item from the free list, as required by the allocation demonstrated in FIG. 2B, and adding an item to the free list, as required by the reclamation demonstrated in FIG. 2C, are both delicate operations. If two different threads were to each cause the operating system to modify the free list at approximately the same time and the component operations of the modifications were temporally interleaved, the free list could be corrupted. For example, if both a first and a second thread were attempting to free different selectors, and the first thread was interrupted between the two constituent operations of the freeing process by all of the operations of the freeing process from the second thread, the selector xe2x80x9cfreedxe2x80x9d would not end up on the list.
As a result, the free list is typically protected by a synchronization mechanism, such as a mutual-exclusion semaphore, that allows only one thread at a time to manipulate the free list. This is indicated in the diagrams by the wavy boundary surrounding the free list. When the operating system, during execution of a particular thread, needs to modify the free list, the operating system xe2x80x9cattempts to acquirexe2x80x9d the synchronization mechanism. If the synchronization mechanism is not xe2x80x9ccurrently acquiredxe2x80x9dxe2x80x94that is, if no other thread has acquired the synchronization mechanism without subsequently releasing itxe2x80x94the acquiring thread is permitted to acquire the synchronization mechanism. The operating system, during execution of the acquiring thread, then adds an item to or removes an item from the free list and releases the synchronization mechanism. If, on the other hand, the synchronization mechanism is currently acquired, the attempting thread is typically suspended (i.e., permitted to execute no further instructions) until the synchronization mechanism is subsequently released.
While the use of a synchronization mechanism to protect the free list prevents the corruption of the free list by preventing threads from modifying it contemporaneously, it also introduces significant overhead into the allocation and reclamation processes. First, synchronization typically requires the execution of an extra series of several administrative instructions for each attempt to acquire and release the synchronization mechanism. Second, the suspension of threads that attempt to acquire the synchronization mechanism when it has been acquired but not released by another thread impedes the progress of the suspended threads. As a result, computer system performance is degraded during periods in which allocation and reclamation occur frequently.
It is an object of the invention to provide a method and system in a computer system for threaded resource allocation and reclamation.
It is another object of the invention to provide a method and system in a computer system for providing available instances of a resource.
It is a further object of the invention to provide a method and system in a computer system for reclaiming available instances of a resource.
It is yet a further object of the invention to provide a method and system for managing free memory selectors.
These and other objects, which will become apparent as the invention is more fully described below, are provided by a method and system for threaded resource allocation and reclamation. The invention provides the advantage of removing the synchronization overhead typically required to perform routine resource allocations and reclamations in a multithreaded system, while at the same time guaranteeing that all free resources are ultimately available to any thread that requests them. In a preferred embodiment, a resource allocation and reclamation facility (xe2x80x9cthe facilityxe2x80x9d), which is preferably integrated into an operating system, manages the allocation and reclamation of available instances of a scarce system resource (xe2x80x9cinstancesxe2x80x9d), such as memory selectors. In addition to a central free list of instances for allocation to any thread (xe2x80x9cthe central free listxe2x80x9d), the facility maintains, for each thread, an individual free list of instances for allocation to that thread only (xe2x80x9cindividual free listsxe2x80x9d). While the central free list is preferably protected by a mutual-exclusion semaphore (xe2x80x9csemaphorexe2x80x9d) to prevent simultaneous access by multiple threads, the individual free lists are not protected by semaphores, since they may each be accessed only by their own thread, and therefore are not subject to simultaneous access.
Briefly, when a thread requests an instance, the facility first attempts to allocate an instance from the thread""s individual free list. This allocation proceeds quickly, because the individual free list is not protected by a semaphore. If the requesting thread""s individual free list is empty, the facility acquires the semaphore that protects the central free list and attempts to allocate an instance from the central free list. If the central free list is empty, the facility suspends the execution of all of the other threads while it transfers instances from the individual free lists to the central free list, one of which it allocates to the requesting thread. When a thread releases an instance that it has finished using, the facility reclaims it by placing the instance on the releasing thread""s individual free list, allowing it to be quickly allocated back to the releasing thread to satisfy a future request.